//匈牙利算法
//hungarian

//用匈牙利算法求给定二分图的最大匹配

//1)基础概念
//二分图:
//二分图B=<X,Y,E>是将B中所有节点分成两个节点子集X和Y(没有重复的节点)
//而且边集E中的每条边的一个端点属于X 另一个属于Y
//染色法判定二分图:
//使用bfs或dfs从起点开始遍历图 对所有节点染上两种颜色(即分成X和Y两集合)
//被扩展节点要染的颜色与将它扩展的那个邻节点的颜色不同(即相邻节点分为不同集合)
//若存在两相邻节点颜色相同则该图不是二分图 否则是二分图
//
//匹配: 
//匹配是图G=<V,E>中边集E的一个子集 该子集中任意两边不相邻 匹配也称作边独立集
//相应的还有点独立集的概念 一般将点独立集简称为独立集 而边独立集就称作匹配
//属于匹配中边的端点的节点是饱和点(匹配点) 不属于的节点是不饱和点(未匹配点)
//最大匹配:
//边数量最多的匹配
//匹配数:
//最大匹配的边数量
//完全 完备 完美匹配:
//图G中所有节点都属于该匹配 即所有节点都是该匹配中边的端点
//完备匹配必然是最大匹配
//
//所有二分匹配算法都基于增广轨定理 即当一个匹配没有增广轨时该匹配就是最大匹配
//交错轨:
//一条简单路径上的边交错的属于匹配 即任意相邻的两边一条属于匹配 另一条不属于匹配
//增广轨:
//一条起点和终点都是未匹配点的交错轨
//
//(Hall提出的)定理: 二分图B=<X,Y,E>有饱和X的匹配当且仅当
//对于X中的任意子集S都有|N(S)|>=|S| 其中N(S)指代S的邻节点集
//即S的邻节点集的节点数量>=S的节点数量
//推论1: 二分图B=<X,Y,E>的X集合中每个节点至少关联k(k>=1)条边 即至少k个邻节点
//Y集合中每个节点至多关联k条边 即至多k个邻节点 则B存在饱和X的匹配
//注意以上两条只是针对于饱和X 即匹配了X集合中所有节点
//推论2: 二分图B=<X,Y,E>有完备匹配的充要条件是|X|=|Y|
//且对于X和Y中任意子集S都有|N(S)|>=|S| 即子集的邻节点集数量>=子集节点数量
//
//Berge定理 增广轨定理: 
//简单无环图G的匹配M是最大匹配的充要条件是图G中不存在M的可扩展路(增广轨)
//Hall定理: 
//二分图B=<X,Y,E>有饱和X的匹配当且仅当对X的任意子集S有|N(S)|>=|S|
//
//匈牙利算法正是基于这两个定理
//该算法既能判断二分图中是否存在完备匹配 又能在完备匹配存在时求出该完备匹配
//但一般题目中只使用它来求二分图的最大匹配 而不去判断该最大匹配是否完备匹配
//
//匈牙利算法:
//匈牙利算法最为流行的方法是通过dfs来实现增广轨的搜索
//对二分图中X集合的每个未匹配的节点i开始查找增广轨
//若找到就修改当前匹配 直到无法找到增广轨结束
//初始时匹配M为空 对X中所有未匹配节点i重复以下步骤: 
//以节点i为增广轨的起点 通过dfs搜索查找该增广轨的终点j
//由增广轨性质可知: 二分图上的增广轨只有路径两头的端点是未匹配点 其余都是匹配点
//所以只要节点j是未匹配点即就是增广轨的终点
//初始时节点i的任意邻节点都未匹配 即第一条增广轨的终点就是节点i的任意邻节点
//这样即可得到一条增广轨 增广轨本质就是用于增大匹配
//二分图中的增广轨从节点i开始 第一条边未匹配 第二条边匹配 第三条边未匹配...
//最后一条边未匹配 必定有奇数条边 且起点终点都未匹配 利用增广轨交错的性质
//将该增广轨第一条边改为匹配 第二条边改为未匹配 第三条边改为匹配...
//最后一条边改为匹配 即该增广轨上的边匹配属性完全颠倒 即可得到比原匹配大1的匹配
//重复以上步骤直到无法继续找出新的增广轨 算法结束
//
//如果需要求完备匹配 在上述的重复步骤中 对于二分图的每个节点i都进行判断
//从节点i出发的搜索若不存在增广轨 则可得到一条交错轨 设该交错轨的节点集合为A
//对于节点子集S=A^X 即S是A与X的交集 判断S是否满足|N(S)|<=|S|即可判断完备匹配
//若存在完备匹配则匈牙利算法最终得到的即为完备匹配
//
//为了方便本文不判断是否存在完备匹配 只求出最大匹配
//
//2)具体实现
//匹配标记技术: 
//设置数组xmatch和ymatch来标记二分图的X和Y集合中节点的匹配的邻节点
//xmatch[i](ymatch[i])指代集合X(Y)中的节点i在匹配中边的邻节点的下标号
//即比如一条边e的属于X集合的端点为节点i 另一属于Y集合的端点为节点j
//则有xmatch[i]==j和ymatch[j]==i
//由二分图性质可知
//X集合中节点i的匹配的邻节点只有一个 而且一定属于集合Y
//而Y集合中节点j的匹配的邻节点只有一个 而且一定属于集合X
//网络上也有只设置一个数组xmatch(或ymatch)的代码实现
//设置xmatch和ymatch两数组虽然存储了相同的重复的信息
//但数组数量的不同对算法的实现有影响 具体在代码中会有说明
//设置两个数组是对匈牙利算法的原本实现
//匹配标记技术和本章前四小节中的路径标记技术是类似的技术 是二分图算法的基础技术
//
//本文引用了"图论讲义 第3章(匹配问题)" 作者"高随祥"
//在众多二分图的网络资料中 "图论讲义"是一份价值极高的中文文档 推荐大家看
//此书原为"图论与网络流理论(中科院研究生院专业基础课)" 作者/讲授"高随祥"
//本节中所有概念与定理都以"图论讲义"为准

//1)设置xmatch和ymatch两个数组

#include "general_head.h"
#include "graph.h"
int dfs_path1(bipartite b, int *visited, int p, int *xmatch, int *ymatch)
{//从p节点进入递归时visited是初始状态 之后的递归visited记录访问状态
	for(int i = 0; i < b.b_yn; ++i)
		//考虑X中节点p在Y集合中的所有可能的邻节点i
		if(!visited[i] && b.b_g[p][i]){
			//若Y集合中的节点i是X集合中节点p的邻节点 且节点i未被访问
			visited[i] = 1;
			if(ymatch[i] == -1 ||
					dfs_path1(b, visited, ymatch[i], xmatch, ymatch)){
				//若Y中的节点i未匹配 则直接匹配该节点 若i已匹配 则进行如下判断
				//从该节点i的匹配节点ymatch[i]开始进行下一轮递归的dfs
				//设ymatch[i]=j 即Y集合中i匹配的节点为j 其中i属于Y j属于X
				//从这个X集合中的j节点开始下一轮dfs
				//设j节点在Y中的邻节点为k节点 j和k的关系与p和i的关系一样
				//若k满足条件ymatch[k] == -1 即找到j的邻节点k(属于Y)是未匹配点
				//则将j和k匹配起来 但是这里需要修改原匹配
				//在上一轮dfs中 原本Y中节点i与X中节点j是一个匹配
				//现在j和k进行匹配 回到上一轮dfs中将p和i匹配起来
				//释放掉原本i和j的匹配关系
				//这样的dfs可以递归多次 若最终可以找到一个新的Y中未匹配点k
				//则dfs中会修改原匹配关系 最大匹配加1
				//若找不到则在上一层函数中遍历X中的下一个节点
				xmatch[p] = i;
				ymatch[i] = p;
				return(1);
			}
		}
	return(0);
}

int hungarian1(bipartite b, int *xmatch, int *ymatch)
{//二分图B分为X和Y两集合
 //X集合有b_xn个节点 下标从0到b_xn-1 Y集合有b_yn个节点 下标从0到b_yn
 //b_g[i][j]若为1指代节点i和节点j之间有边 若为0指代i和j之间无边
 //而且保证节点i属于集合X 节点j属于Y 不会出现i属于Y而j属于X的情况
 //xmatch[i](ymatch[i])指代X(Y)集合中节点i在最大匹配中的邻节点的下标号j
 //邻节点j一定属于Y(X)集合
 //若xmatch[i](ymatch[i])为-1则节点i未匹配
 //因为节点下标从0起始 所以用-1标记未匹配状态
 //数组xmatch和ymatch中的节点下标号i并不是该节点在二分图中的唯一标记
 //而是它在X和Y中的唯一标记 X集合和Y集合中都存在下标为i的节点 但并非同一节点
 //二分图所有节点由X集合与Y集合中节点组合而成
 //返回二分图中最大匹配数max_match和最大匹配
 //最大匹配存储于xmatch和ymatch中 长度都为MAX 存储相同的信息
	//由于节点下标从0开始所以使用-1标记节点未匹配
	memset(xmatch, -1, MAX * sizeof(int));
	memset(ymatch, -1, MAX * sizeof(int));
	int visited[MAX], max_match(0);
	for(int i = 0; i < b.b_xn; ++i)
		//遍历X集合中的未匹配的每个节点i
		if(xmatch[i] == -1){
			//当然二分图中集合X和Y可以颠倒 但所有的相应信息都需要颠倒
			//visited数组用于dfs遍历中标记Y集合中的节点是否被访问过
			//注意该数组只标记Y集合中的节点
			//即visited[i]中的节点i是Y集合中下标为i的节点
			//每次dfs遍历开始时都刷新visited数组
			memset(visited, 0, MAX * sizeof(int));
			//从X集合中未匹配的节点i开始dfs寻找一条增广轨
			//若找到返回最大匹配加1 若找不到返回0
			if(dfs_path1(b, visited, i, xmatch, ymatch))
				++max_match;
		}
	return(max_match);
}


//2)设置ymatch一个数组

int dfs_path2(bipartite b, int *visited, int p, int *ymatch)
{
	for (int i = 0; i < b.b_yn; ++i)
		if (!visited[i] && b.b_g[p][i]) {
			visited[i] = 1;
			if (ymatch[i] == -1 ||
					dfs_path2(b, visited, ymatch[i], ymatch)) {
				//没有xmatch数组只设置ymatch即可
				ymatch[i] = p;
				return(1);
			}
		}
	return(0);
}

int hungarian2(bipartite b, int *ymatch)
{
	memset(ymatch, -1, MAX * sizeof(int));
	int visited[MAX], max_match = 0;
	for (int i = 0; i < b.b_xn; ++i) {
		//没有xmatch数组 无法验证X集合中节点i是否未匹配
		memset(visited, 0, MAX * sizeof(int));
		if (dfs_path2(b, visited, i, ymatch))
			++max_match;
	}
	return(max_match);
}
